home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 42 / Amiga Format AFCD42 (Issue 126, Aug 1999).iso / -serious- / programming / other / jikes / src / spell.h < prev    next >
C/C++ Source or Header  |  1999-05-14  |  4KB  |  130 lines
  1. // $Id: spell.h,v 1.2 1999/02/25 18:11:37 shields Exp $
  2. //
  3. // This software is subject to the terms of the IBM Jikes Compiler
  4. // License Agreement available at the following URL:
  5. // http://www.ibm.com/research/jikes.
  6. // Copyright (C) 1996, 1999, International Business Machines Corporation
  7. // and others.  All Rights Reserved.
  8. // You must accept the terms of that agreement to use this software.
  9. //
  10. #ifndef spell_INCLUDED
  11. #define spell_INCLUDED
  12.  
  13. #include "config.h"
  14. #include "case.h"
  15.  
  16. class Spell
  17. {
  18.     static inline int Min(int x, int y) { return (x < y ? x : y); }
  19.  
  20. public:
  21.     static int Index(wchar_t *str1, wchar_t *str2)
  22.     {
  23.         int len1 = wcslen(str1),
  24.             len2 = wcslen(str2);
  25.  
  26.         wchar_t *s1 = new wchar_t[len1 + 1],
  27.                 *s2 = new wchar_t[len2 + 1];
  28.  
  29.         for (int i = 0; i < len1; i++)
  30.             s1[i] = Case::ToAsciiLower(str1[i]);
  31.         s1[len1] = U_NULL;
  32.  
  33.         for (int j = 0; j < len2; j++)
  34.             s2[j] = Case::ToAsciiLower(str2[j]);
  35.         s2[len2] = U_NULL;
  36.  
  37.         if (len1 == 1 && len2 == 1)
  38.         {
  39.             //
  40.             //  Singleton mispellings:
  41.             //
  42.             //  ;      <---->     ,
  43.             //
  44.             //  ;      <---->     :
  45.             //
  46.             //  .      <---->     ,
  47.             //
  48.             //  '      <---->     "
  49.             //
  50.             if ((s1[0] == U_SEMICOLON    &&  s2[0] == U_COMMA)  ||
  51.                 (s1[0] == U_COMMA        &&  s2[0] == U_SEMICOLON)  ||
  52.                 (s1[0] == U_SEMICOLON    &&  s2[0] == U_COLON)  ||
  53.                 (s1[0] == U_COLON        &&  s2[0] == U_SEMICOLON)  ||
  54.                 (s1[0] == U_DOT          &&  s2[0] == U_COMMA)  ||
  55.                 (s1[0] == U_COMMA        &&  s2[0] == U_DOT)  ||
  56.                 (s1[0] == U_SINGLE_QUOTE &&  s2[0] == U_DOUBLE_QUOTE)  ||
  57.                 (s1[0] == U_DOUBLE_QUOTE &&  s2[0] == U_SINGLE_QUOTE))
  58.                     return 3;
  59.         }
  60.  
  61.         //
  62.         // Scan the two strings. Increment "match" count for each match.
  63.         // When a transposition is encountered, increase "match" count
  64.         // by two but count it as an error. When a typo is found, skip
  65.         // it and count it as an error. Otherwise we have a mismatch; if
  66.         // one of the strings is longer, increment its index, otherwise,
  67.         // increment both indices and continue.
  68.         //
  69.         // This algorithm is an adaptation of a boolean misspelling
  70.         // algorithm proposed by Juergen Uhl.
  71.         //
  72.         int count = 0,
  73.             prefix_length = 0,
  74.             num_errors = 0,
  75.             i1 = 0,
  76.             i2 = 0;
  77.  
  78.         while ((i1 < len1)  &&  (i2 < len2))
  79.         {
  80.             if (s1[i1] == s2[i2])
  81.             {
  82.                 count++;
  83.                 i1++;
  84.                 i2++;
  85.                 if (num_errors == 0)
  86.                     prefix_length++;
  87.             }
  88.             else if (s1[i1 + 1] == s2[i2]  &&  s1[i1] == s2[i2 + 1])
  89.             {
  90.                 count += 2;
  91.                 i1 += 2;
  92.                 i2 += 2;
  93.                 num_errors++;
  94.             }
  95.             else if (s1[i1 + 1] == s2[i2 + 1])
  96.             {
  97.                 i1++;
  98.                 i2++;
  99.                 num_errors++;
  100.             }
  101.             else
  102.             {
  103.                 if ((len1 - i1) > (len2 - i2))
  104.                      i1++;
  105.                 else if ((len2 - i2) > (len1 - i1))
  106.                      i2++;
  107.                 else
  108.                 {
  109.                     i1++;
  110.                     i2++;
  111.                 }
  112.                 num_errors++;
  113.             }
  114.         }
  115.  
  116.         if (i1 < len1  ||  i2 < len2)
  117.             num_errors++;
  118.  
  119.         if (num_errors > (Min(len1, len2) / 6 + 1))
  120.              count = prefix_length;
  121.  
  122.         delete [] s1;
  123.         delete [] s2;
  124.  
  125.         return (count * 10 / (len1 + num_errors));
  126.     }
  127. };
  128.  
  129. #endif // #ifndef spell_INCLUDED
  130.